Grafo dividido

Un grafo dividido, dividido en un clique y un conjunto independiente.

En la teoría de grafos, una rama de las matemáticas, un grafo dividido (o el grafo split) es un grafo en el que los vértices se pueden dividir en una clique y un conjunto independiente . Los grafos divididos fueron estudiados por primera vez por Földes y Hammer (1977), e introducido independientemente por Tyshkevich y Cherniak (1979).​

Un grafo dividido puede tener más de una partición en un clique y un conjunto independiente; por ejemplo, el camino a–b–c es un grafo dividido, cuyos vértices se pueden dividir de tres maneras diferentes:

1. el clique {a, b} y el conjunto independiente {c}
2. el clique {b, c} y el conjunto independiente {a}
3. el clique {b} y el conjunto independiente {a, c}

Los grafos divididos se pueden caracterizar en términos de sus subgrafos inducidos prohibidos : un gráfico se divide si y solo si ningún subgrafo inducido es un ciclo en cuatro o cinco vértices, o un par de aristas disjuntas (el complemento de un 4-ciclo).​

Relación con otras familias de grafos

A partir de la definición, los grafos divididos están claramente cerrados bajo complementación .​ Otra caracterización de los grafos divididos implica la complementación: son grafos cordales cuyos complementos también son cordales.​ Así como los grafos cordales son los grafos de intersección de los subárboles de los árboles, los grafos divididos son los grafos de intersección de distintas subestrellas de los grafos de estrellas .​ Casi todos los grafos cordales son grafos divididos; es decir, en el límite cuando n tiende a infinito, la fracción de gráficos cordales de n vértices que se dividen se aproxima a uno.​

Debido a que los grafos cordales son perfectos, también lo son los grafos divididos. Los grafos de división doble, una familia de grafos derivados de grafos divididos al duplicar cada vértice (de modo que la camarilla llega a inducir un antiemparejamiento y el conjunto independiente viene a inducir un emparejamiento), figura de manera destacada como una de las cinco clases básicas de grafos perfectos de los cuales todos los demás pueden formarse en la prueba de Chudnovsky et al. (2006) del teorema del gráfico perfecto fuerte .

Si un grafos es a la vez un grafos dividido y un grafos de intervalos, entonces su complemento es tanto un gráfico dividido como un grafo de comparabilidad, y viceversa. Los grafos de comparabilidad dividida y, por lo tanto, también los grafos de intervalo dividido, se pueden caracterizar en términos de un conjunto de tres subgrafos inducidos prohibidos.​ Los cografos divididos son exactamente los grafos de umbral . Los grafos de permutación dividida son exactamente los grafos de intervalo que tienen complementos de grafo de intervalo;​ estos son los grafos de permutación de permutaciones combinadas sesgadas . [9] Los grafos divididos tienen el número cocromático 2.

Problemas algorítmicos

Sea G un grafo dividido, dividido en una camarilla C y un conjunto independiente i . Entonces, cada clique máximo en un grafo dividido es C en sí mismo o la vecindad de un vértice en i . Por lo tanto, es fácil identificar el clique máximo y, complementariamente, el conjunto independiente máximo en un grafo dividido. En cualquier grafo dividido, una de las siguientes tres posibilidades debe ser verdadera:​

1. Existe un vértice x en i tal que C ∪ {x} es completo. En este caso, C ∪ {x} es un clique máxima e i es un conjunto independiente máximo.
2. Existe un vértice x en C tal que i ∪ {x} es independiente. En este caso, i ∪ {x} es un conjunto independiente máximo y C es un clique máxima.
3. C es un clique máximo e i es un conjunto independiente máximo. En este caso, G tiene una partición única (C, i) en un clique y un conjunto independiente, C es el clique máximo e i es el conjunto independiente máximo.

Algunos otros problemas de optimización que son NP-completos en familias de grafos más generales, incluida la coloración de grafos, son igualmente sencillos en grafos divididos. Encontrar un ciclo hamiltoniano sigue siendo NP-completo incluso para grafos divididos que son grafos fuertemente cordales .​ También es bien sabido que el problema del Conjunto Dominante Mínimo sigue siendo NP-completo para grafos divididos.​

Secuencias de grado

Una propiedad notable de los grafos divididos es que pueden reconocerse únicamente a partir de sus secuencias de grados . Sea la secuencia de grados de un gráfico G $d_{1}\geq d_{2}\geq \ldots \geq d_{n}$, y sea m el mayor valor de i tal que $d_{i}\geq i-1$ . Entonces G es un grafo dividido si y solo si

$\sum _{i=1}^{m}d_{i}=m(m-1)+\sum _{i=m+1}^{n}d_{i}.$

Si este es el caso, entonces los m vértices con los grados más grandes forman un clique máxima en G, y los vértices restantes constituyen un conjunto independiente.​

La división de un grafo arbitrario mide hasta qué punto esta desigualdad no se cumple. Si un grafo no es un grafo dividido, entonces se puede obtener la secuencia más pequeña de inserciones y eliminaciones de bordes que lo convierten en un gráfico dividido sumando todos los bordes que faltan entre los m vértices con los grados más grandes y eliminando todos los bordes entre pares de los vértices restantes; la división cuenta el número de operaciones en esta secuencia. [14]

Contando gráficos divididos

Royle (2000) mostró que los grafos divididos en n vértices con n tienen una correspondencia biunívoca con ciertas familias de Sperner. Utilizando este hecho, determinó una fórmula para el número de gráficos divididos no isomorfos en n vértices. Para valores pequeños de n, a partir de n = 1, estos números son

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696,... (sucesión A048194 en OEIS) .

Este resultado enumerativo también fue probado anteriormente por Tyshkevich y Chernyak (1990) .

Bibliografía

• Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985), «Almost all chordal graphs split», J. Austral. Math. Soc., A 38 (2): 214-221, MR 0770128, doi:10.1017/S1446788700023077 ..
• Bertossi, Alan A. (1984), «Dominating sets for split and bipartite graphs», Information Processing Letters 19: 37-40, doi:10.1016/0020-0190(84)90126-1 ..
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X, (requiere registro) ..
• Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), «The strong perfect graph theorem», Annals of Mathematics 164 (1): 51-229, MR 2233847, arXiv:math/0212070, doi:10.4007/annals.2006.164.51 ..
• Földes, Stéphane; Hammer, Peter Ladislaw (1977a), «Split graphs», Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Congressus Numerantium XIX, Winnipeg: Utilitas Math., pp. 311-315, MR 0505860 ..
• Földes, Stéphane; Hammer, Peter Ladislaw (1977b), «Split graphs having Dilworth number two», Canadian Journal of Mathematics 29 (3): 666-672, MR 0463041, doi:10.4153/CJM-1977-069-1 ..
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7, MR 0562306 ..
• Hammer, Peter Ladislaw; Simeone, Bruno (1981), «The splittance of a graph», Combinatorica 1 (3): 275-284, MR 0637832, doi:10.1007/BF02579333 ..
• Kézdy, André E.; Snevily, Hunter S.; Wang, Chi (1996), «Partitioning permutations into increasing and decreasing subsequences», Journal of Combinatorial Theory, Series A 73 (2): 353-359, MR 1370138, doi:10.1016/S0097-3165(96)80012-4 ..
• McMorris, F. R.; Shier, D. R. (1983), «Representing chordal graphs on K_1,n», Commentationes Mathematicae Universitatis Carolinae 24: 489-494, MR 0730144 ..
• Merris, Russell (2003), «Split graphs», European Journal of Combinatorics 24 (4): 413-430, MR 1975945, doi:10.1016/S0195-6698(03)00030-1 ..
• Müller, Haiko (1996), «Hamiltonian Circuits in Chordal Bipartite Graphs», Discrete Mathematics 156: 291-298, doi:10.1016/0012-365x(95)00057-4 ..
• Royle, Gordon F. (2000), «Counting set covers and split graphs», Journal of Integer Sequences 3 (2): 00.2.6, MR 1778996 ..
• Tyshkevich, Regina I. (1980), «[The canonical decomposition of a graph]», Doklady Akademii Nauk SSSR (en russian) 24: 677-679, MR 0587712 .
• Tyshkevich, Regina I.; Chernyak, A. A. (1979), «Canonical partition of a graph defined by the degrees of its vertices», Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk (en russian) 5: 14-26, MR 0554162 ..
• Tyshkevich, Regina I.; Chernyak, A. A. (1990), Mat. Zametki (en russian) 48 (6): 98-105, MR 1102626 http://mi.mathnet.ru/eng/mz3413  .. Translated as "Yet another method of enumerating unmarked combinatorial objects" (1990), Mathematical notes of the Academy of Sciences of the USSR 48 (6): 1239–1245, doi 10.1007/BF01240267.
• Tyshkevich, Regina I.; Melnikow, O. I.; Kotov, V. M. (1981), «On graphs and degree sequences: the canonical decomposition», Kibernetika (en russian) 6: 5-8, MR 0689420 ..
• Voss, H.-J. (1985), «Note on a paper of McMorris and Shier», Commentationes Mathematicae Universitatis Carolinae 26: 319-322, MR 0803929 ..

Otras lecturas

• Un capítulo sobre gafos divididos aparece en el libro de Martin Charles Golumbic, "Teoría de grafos algorítmicos y grafos perfectos".

• Datos: Q3893853